package OJPractice;

import MAIN.ListNode;

import java.util.ArrayList;
import java.util.List;

public class dfs1 {
    // 合并两个有序链表
    public ListNode mergeTwoLists(ListNode list1, ListNode list2) {
        if (list1 == null) return list2;
        if (list2 == null) return list1;
        if (list1.value < list2.value) {
            list1.next = mergeTwoLists(list1.next, list2);
            return list1;
        } else {
            list2.next = mergeTwoLists(list1, list2.next);
            return list2;
        }
    }
    //  反转链表
    public ListNode reverseList(ListNode head) {
        if (head == null || head.next == null) return head;
        ListNode newHead = reverseList(head.next);
        head.next.next = head;
        head.next = null;
        return newHead;
    }
    //  两两交换链表中的节点
    public ListNode swapPairs(ListNode head) {
        if (head == null || head.next == null) return head;
        ListNode tmp = swapPairs(head.next.next);
        ListNode newHead = head.next;
        newHead.next = head;
        head.next = tmp;
        return newHead;
    }
    // Pow(x, n)
    public double myPow(double x, int n) {
        return n < 0 ? 1.0 / pow(x, n) : pow(x, n);
    }
    public double pow(double x, int n) {
        if (n == 0) return 1;
        double tmp = pow(x, n / 2);
        return n % 2 == 0 ? tmp * tmp : tmp * tmp * x;
    }
    // 计算布尔二叉树的值
    public boolean evaluateTree(TreeNode root) {
        if(root.left == null) return root.val == 0 ? false : true;
        boolean leftTree = evaluateTree(root.left);
        boolean rightTree = evaluateTree(root.right);
        if (root.val == 2) return leftTree || rightTree;
        else return leftTree && rightTree;
    }
    // 求根节点到叶节点数字之和
    public int sumNumbers(TreeNode root) {
        return dfs(root, 0);
    }
    public int dfs(TreeNode root, int preSum) {
        preSum = preSum * 10 + root.val;
        if (root.left == null && root.right == null) return preSum;
        int ret = 0;
        if (root.left != null) ret += dfs(root.left, preSum);
        if (root.right != null) ret += dfs(root.right, preSum);
        return ret;
    }
    // 二叉树剪枝
    public TreeNode pruneTree(TreeNode root) {
        if (root == null) return null;
        root.left = pruneTree(root.left);
        root.right = pruneTree(root.right);
        if (root.left == null && root.right == null && root.val == 0) {
            root = null;
        }
        return root;
    }
    // 子集
    List<List<Integer>> ret;
    List<Integer> path;
    public List<List<Integer>> subsets(int[] nums) {
        ret = new ArrayList<>();
        path = new ArrayList<>();
        dfs(nums, 0);
        return ret;
    }
    public void dfs(int[] arr, int pos) {
        if (pos == arr.length) {
            ret.add(new ArrayList<>(path));
            return;
        }
        // 函数体
        // 选
        path.add(arr[pos]);
        dfs(arr, pos + 1);
        path.remove(path.size() - 1);
        // 不选
        dfs(arr, pos + 1);
    }

}
